Java Technologies Divide and Conquer কৌশলের ধারণা গাইড ও নোট

Divide and Conquer

Divide and Conquer হল একটি অ্যালগরিদমিক কৌশল যা একটি বড় সমস্যাকে ছোট ছোট উপ-সমস্যায় বিভক্ত করে এবং প্রতিটি উপ-সমস্যার সমাধান করে, তারপর তাদের একত্রিত করে মূল সমস্যার সমাধান পাওয়া যায়। এই কৌশলটি বেশিরভাগ কার্যকরী অ্যালগরিদমে ব্যবহৃত হয়, যেমন Merge Sort এবং Quick Sort।

Divide and Conquer পদ্ধতির তিনটি প্রধান ধাপ:

1. Divide: সমস্যাটিকে ছোট ছোট উপ-সমস্যায় বিভক্ত করা।
2. Conquer: প্রতিটি উপ-সমস্যা সমাধান করা।
3. Combine: উপ-সমস্যাগুলির সমাধান একত্রিত করা।

1. Merge Sort

Merge Sort একটি Divide and Conquer অ্যালগরিদম যা একটি অ্যারে বা তালিকাকে বিভক্ত করে এবং প্রতিটি ভাগকে সজ্জিত করে, তারপর ঐ সমস্ত ভাগগুলোকে একত্রিত করে সাজানো (merge) করে। এটি একটি Stable Sorting Algorithm এবং এটি সর্বদা O(n log n) টাইম কমপ্লেক্সিটিতে কাজ করে, যা এটি একটি দক্ষ সাজানো অ্যালগরিদম বানায়।

Merge Sort এর প্রধান স্টেপ:

1. অ্যারেটি মাঝখানে ভাগ করুন (Divide).
2. প্রতিটি ভাগকে সজ্জিত করুন (Conquer).
3. সজ্জিত ভাগগুলোকে একত্রিত করুন (Combine).

Merge Sort Implementation:

public class MergeSort {
    // Method to merge two halves
    public static void merge(int[] arr, int left, int mid, int right) {
        // Find the size of two subarrays to be merged
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Create temporary arrays
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        // Copy data to temp arrays leftArray[] and rightArray[]
        System.arraycopy(arr, left, leftArray, 0, n1);
        System.arraycopy(arr, mid + 1, rightArray, 0, n2);

        // Merge the temp arrays back into arr[]
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        // Copy any remaining elements of leftArray[]
        while (i < n1) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        // Copy any remaining elements of rightArray[]
        while (j < n2) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }

    // Method to sort the array using merge sort
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            // Recursively divide the array into two halves
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // Merge the sorted halves
            merge(arr, left, mid, right);
        }
    }

    // Method to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};

        System.out.println("Unsorted Array:");
        printArray(arr);

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("Sorted Array using Merge Sort:");
        printArray(arr);  // Output: 3 9 10 27 38 43 82
    }
}

ব্যাখ্যা:

• merge: দুইটি সজ্জিত অংশকে একত্রিত (merge) করে একটি সজ্জিত অংশ তৈরি করে।
• mergeSort: এটি রিকার্সিভভাবে অ্যারেটি দুই ভাগে ভাগ করে এবং পরবর্তীতে তাদেরকে সজ্জিত করে।
• Time Complexity: O(n log n) - এখানে n হল অ্যারের সাইজ এবং log n হল বিভাজনের স্তর সংখ্যা।

2. Quick Sort

Quick Sort একটি Divide and Conquer অ্যালগরিদম যা একে একে এলিমেন্টগুলোকে এমনভাবে ভাগ করে যে প্রতিটি ভাগে একটির চেয়ে বড় এবং একটির চেয়ে ছোট উপাদান থাকবে। এটি "partitioning" কৌশল ব্যবহার করে এবং সবচেয়ে দক্ষ সাজানো অ্যালগরিদমগুলোর মধ্যে একটি।

Quick Sort এর প্রধান স্টেপ:

1. একটি পিভট নির্বাচন করুন (এটি সাধারণত অ্যারের প্রথম, শেষ, বা মাঝখানের উপাদান হতে পারে)।
2. অ্যারের উপাদানগুলো এমনভাবে সজ্জিত করুন যাতে পিভটের বাম দিকে ছোট উপাদান এবং ডান দিকে বড় উপাদান থাকে।
3. পুনরায় সাব-অ্যারেগুলির উপর Quick Sort প্রয়োগ করুন।

Quick Sort Implementation:

public class QuickSort {
    // Method to perform partitioning
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // Choosing the last element as pivot
        int i = (low - 1);  // Index of smaller element

        // Re-arrange elements
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Swap arr[i+1] and arr[high] (pivot element)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;  // Return the pivot index
    }

    // Method to implement quick sort
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition the array
            int pi = partition(arr, low, high);

            // Recursively sort the sub-arrays
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    // Method to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};

        System.out.println("Unsorted Array:");
        printArray(arr);

        quickSort(arr, 0, arr.length - 1);

        System.out.println("Sorted Array using Quick Sort:");
        printArray(arr);  // Output: 3 9 10 27 38 43 82
    }
}

ব্যাখ্যা:

• partition: এটি একটি পিভট নির্বাচন করে এবং অ্যারের উপাদানগুলোকে পিভটের তুলনায় ছোট এবং বড় উপাদানে ভাগ করে।
• quickSort: এটি রিকার্সিভভাবে অ্যারের দুটি ভাগে (পিভটের বাম এবং ডান) Quick Sort প্রয়োগ করে।
• Time Complexity: O(n log n) (গড় ক্ষেত্রে), তবে worst case O(n²) হতে পারে যদি পিভট সঠিকভাবে নির্বাচিত না হয়।

3. Merge Sort vs Quick Sort

সারাংশ

Merge Sort এবং Quick Sort হল দুটি জনপ্রিয় Divide and Conquer অ্যালগরিদম যা দ্রুত এবং কার্যকরীভাবে ডেটা সজ্জিত করতে ব্যবহৃত হয়।

• Merge Sort একটি স্টেবল অ্যালগরিদম যা সর্বদা O(n log n) টাইম কমপ্লেক্সিটিতে কাজ করে, তবে এটি অতিরিক্ত মেমরি ব্যবহার করে।
• Quick Sort সাধারণত দ্রুত কাজ করে, কিন্তু O(n²) হতে পারে যদি পিভট সঠিকভাবে নির্বাচিত না হয়। এটি ইনপ্লেস কাজ করে, অর্থাৎ অতিরিক্ত মেমরি ব্যবহারের প্রয়োজন পড়ে না।